#include "BinarySortTree.h"

BTNode* CreateNode(ElementType element)
{
    BTNode *newNode = (BTNode *)malloc(sizeof(BTNode));
    if (newNode == NULL)
    {
        printf("创建新节点失败\n");
        return NULL;
    }
    newNode->data = element;
    newNode->left = NULL;
    newNode->right = NULL;
    newNode->parent = NULL;
    return newNode;
}

void InitBSTree(BSTree *tree)
{
    tree->root = NULL;
}

void InsertNode(BTNode *node, ElementType element)
{
    if (node == NULL)
    {
        return;
    }
    if (node->data > element && node->left == NULL)
    {
        node->left = CreateNode(element);
        if (node->left == NULL)
            return;
        node->left->parent = node;
        return;
    }
    if (node->data < element && node->right == NULL)
    {
        node->right = CreateNode(element);
        if (node->right == NULL)
            return;
        node->right->parent = node;
        return;
    }
    if (node->data > element)
    {
        InsertNode(node->left, element);
    }
    if (node->data < element)
    {
        InsertNode(node->right, element);
    }
}

void InsertElement(BSTree *tree, ElementType element)
{
    if (tree->root == NULL)
    {
        tree->root = CreateNode(element);
    }
    else
    {
        InsertNode(tree->root, element);
    }
    
}

void PrevPrintNode(BTNode *node)
{
    if (node == NULL)
        return;
    printf("%d ", node->data);
    PrevPrintNode(node->left);
    PrevPrintNode(node->right);
}

void PrevPrint(BSTree *tree)
{
    PrevPrintNode(tree->root);
    printf("\n");
}

void MidPrintNode(BTNode *node)
{
    if (node == NULL)
        return;
    MidPrintNode(node->left);
    printf("%d ", node->data);
    MidPrintNode(node->right);
}

void MidPrint(BSTree *tree)
{
    MidPrintNode(tree->root);
    printf("\n");
}

void PostPrintNode(BTNode *node)
{
    if (node == NULL)
        return;
    PostPrintNode(node->left);
    PostPrintNode(node->right);
    printf("%d ", node->data);
}

void PostPrint(BSTree *tree)
{
    PostPrintNode(tree->root);
    printf("\n");
}

BTNode* FindNode(BTNode *node, ElementType element)
{
    if (node == NULL)
        return NULL;
    if (node ->data == element)
        return node;
    else if (node->data > element)
    {
        return FindNode(node->left, element);
    }
    else
    {
        return FindNode(node->right, element);
    }
}

BTNode *FindElement(BSTree *tree, ElementType element)
{
    return FindNode(tree->root, element);
}

bool IsLeftChild(BTNode *node)
{
    if (node->parent == NULL)
        return false;
    if (node->parent->left == node) 
        return true;
    else 
        return false;
}

void RemoveElement(BSTree *tree, ElementType element)
{
    BTNode *target = FindElement(tree, element);
    if (target == NULL)
        return;
    if (target->left == NULL && target->right == NULL)
    {
        // 找到的是根节点
        if (target->parent == NULL)
        {
            free(target);
            tree->root = NULL;
            return;
        }
        if (IsLeftChild(target) == true)
        {
            target->parent->left = NULL;
        }
        else 
        {
            target->parent->right = NULL;
        }
        free(target);
        return;
    }
    else if (target->right == NULL)
    {
        if (target->parent == NULL)
        {
            tree->root = target->left;
            free(target);
            return;
        }
        // 左孩子接到双亲的节点上
        target->left->parent = target->parent;
        if (IsLeftChild(target) == true)
        {
            target->parent->left = target->left;
        }
        else
        {
            target->parent->right = target->left;
        }
        free(target);
    }
    else if (target->left == NULL)
    {
        if (target->parent == NULL)
        {
            tree->root = target->right;
            free(target);
            return;
        }
        target->right->parent = target->parent;
        if (IsLeftChild(target) == true)
        {
            target->parent->left = target->right;
        }
        else
        {
            target->parent->right = target->right;
        }
        free(target);
    }
    else if (target->left != NULL && target->right != NULL)
    {
        // 找右子树中最小的点
        BTNode *MinNode = target->right;
        while (MinNode->left != NULL)
        {
            MinNode = MinNode->left;
        }
        target->data = MinNode->data;
        // 右孩子就是右边子树最小的节点
        if (MinNode->parent == target)
        {
            target->right = MinNode->right;
        }
        else
        {
            // 最小左节点可能存在右节点
            MinNode->parent->left = MinNode->right;
        }
        free(MinNode);
    }
}
